public class Solution3 {
    public static int[] dx = {1, 0};
    public static int[] dy = {0, 1};
    public static int m,n;
    public static int cnt;
    public static int ret;
    public static boolean[][] vis;

    public static void main(String[] args) {
        System.out.println(wardrobeFinishing(4, 7, 5));
    }

    public static int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m;
        n = _n;
        cnt = _cnt;
        vis = new boolean[m][n];
        vis[0][0] = true;
        ret++;
        dfs(0,0);
        return ret;
    }

    public static void dfs(int i, int j) {
        for(int k = 0; k < 2; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && check(x,y) && vis[x][y] == false) {
                vis[x][y] = true;
                ret++;
                dfs(x, y);
            }
        }
    }

    public static boolean check(int i, int j) {
        int tmp = 0;
        while(i != 0) {
            tmp += i % 10;
            i /= 10;
        }
        while(j != 0) {
            tmp += j % 10;
            j /= 10;
        }
        if(tmp <= cnt) {
            return true;
        }else {
            return false;
        }
    }
}
